/**
 * 
 */

/**
 * @author reda
 *
 */
public class QuickSortHead {
	
	public static int[] input;

	public static void quickSort(int A[]){
		int n = A.length;
		sort(0,n-1);
	}
	public static void sort( int head, int tail){
		printTable(input);
		if (head==tail)
			return;
		int pivot = head+(tail-head)/2;
		System.out.println("\n pivot :"+pivot);
		swap(input,head,pivot);
		int k=head;
		for(int i=head+1;i<=tail;i++){
		
			if (input[head]>input[i]){
				swap(input,i,++k);
			}
		}
		swap(input,head,k);
		
		if(head<k){
			System.out.println();
			System.out.println("right recursion  "+"head: "+head+"  tail: "+k);
			sort(head,k-1);
		}
	
		if(tail>k)
		{
			System.out.println();
			System.out.println("left recursion  "+"head: "+k+"  tail: "+tail);
			sort(k+1,tail);
		}
			
	}
	
	private static void swap(int A[],int i, int j){
		int temp;
		temp = A[i];
		A[i]=A[j];
		A[j]=temp;
	}
	
	private static void printTable(int A[]){
		int n = A.length ;
		System.out.println("\n");
		for(int i=0;i<n;i++)
			System.out.print(A[i]+"\t");
	}

	/**
	 * @param args
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
